package binary_tree


type NodeWithParent struct {
	Val int
	Left *NodeWithParent
	Right *NodeWithParent
	Parent *NodeWithParent
}

func GetNextNode(node *NodeWithParent) *NodeWithParent {
	if node == nil {return nil}
	if node.Right != nil {
		return GetMostLeftNode(node.Right)
	} else {
		parent := node.Parent
		for parent != nil && node != parent.Right {
			node = parent
			parent = node.Parent
		}
		return parent
	}
}

func GetMostLeftNode(node *NodeWithParent) *NodeWithParent{
	if node.Left != nil {
		node = node.Left
	}
	return node
}